//给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。 
//
// 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 
//
// 你可以假设除了整数 0 之外，这个整数不会以零开头。 
//
// 
//
// 示例 1： 
//
// 
//输入：digits = [1,2,3]
//输出：[1,2,4]
//解释：输入数组表示数字 123。
// 
//
// 示例 2： 
//
// 
//输入：digits = [4,3,2,1]
//输出：[4,3,2,2]
//解释：输入数组表示数字 4321。
// 
//
// 示例 3： 
//
// 
//输入：digits = [0]
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= digits.length <= 100 
// 0 <= digits[i] <= 9 
// 
// Related Topics 数组 数学 👍 1018 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution0066 {

    /**
     * [66]加一 : 数字加一规律(当前位数是 9 就进位, 不是 9 就 +1 返回)
     * <p>
     * 时间复杂度: O(n)
     * <br>
     * 空间复杂度: 0(n)
     */
    public int[] plusOne(int[] digits) {
        int length = digits.length;

        // 是 9 就进位, 不是 9 就 +1 返回
        for (int i = length - 1; i >= 0; i--) { // time n
            if (digits[i] != 9) {
                digits[i] = ++digits[i];
                return digits;
            } else {
                digits[i] = 0;
            }
        }

        // 全是 9
        int[] ret = new int[length + 1]; // space n
        ret[0] = 1;
        return ret;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


class Test0066 {
    public static void main(String[] args) {
        int[] digits = {1, 2, 3};
        int[] digits2 = {4, 3, 2, 1};
        int[] digits3 = {0};
        int[] digits4 = {1, 3, 2, 9};
        int[] digits5 = {9, 9, 9, 9};

        System.out.println(Arrays.toString(plusOne2(digits)));
        System.out.println(Arrays.toString(plusOne2(digits2)));
        System.out.println(Arrays.toString(plusOne2(digits3)));
        System.out.println(Arrays.toString(plusOne2(digits4)));
        System.out.println(Arrays.toString(plusOne2(digits5)));
    }


    /**
     * 将数组转成数组后加一, 在切分成数组; 用例不通过, 超过 int 或 long 的范围就报错了
     * <p>
     * 时间复杂度: O(2n) = O(n)
     * <br>
     * 空间复杂度: O(2n) = O(n)
     */
    public static int[] first(int[] digits) {
        StringBuilder num = new StringBuilder();
        for (int digit : digits) { // time n
            num.append(digit);
        }
        int ret = Integer.parseInt(num.toString()) + 1;
        String[] split = String.valueOf(ret).split(""); // space n
        int[] arr = new int[split.length]; // space n
        for (int i = 0; i < split.length; i++) { // time n
            arr[i] = Integer.parseInt(split[i]);
        }
        return arr;
    }

    /**
     * 将数组转成数组后加一, 在切分成数组; 用例不通过, 超过 int 或 long 的范围就报错了
     * <p>
     * 时间复杂度: O(2n) = O(n)
     * <br>
     * 空间复杂度: O(2n) = O(n)
     */
    public static int[] firstOptimization(int[] digits) {

        int num = 1;
        int mi = digits.length - 1;
        for (int digit : digits) { // time n
            num += (digit * Math.pow(10, mi));
            mi--;
        }

        String[] split = String.valueOf(num).split(""); // space n
        int[] ret = new int[split.length]; // space n
        for (int i = 0; i < split.length; i++) { // time n
            ret[i] = Integer.parseInt(split[i]);
        }
        return ret;
    }

    public static int[] plusOne(int[] digits) {
        int length = digits.length;
        int tailIndex = length - 1;

        // 最简单的情况, 个位 +1 直接返回
        if (digits[tailIndex] != 9) {
            digits[tailIndex] = ++digits[tailIndex];
            return digits;
        }

        // 进位了, 最后一位处理成 0
        digits[tailIndex] = 0;
        // 从倒数第二位开始, 是 9 就进位, 不是 9 就 +1 返回
        for (int i = tailIndex - 1; i >= 0; i--) { // time n
            // 如果当前位不为 9
            if (digits[i] != 9) {
                digits[i] = ++digits[i];
                return digits;
            } else {
                digits[i] = 0;
            }
        }

        // 全是 9
        int[] ret = new int[length + 1]; // space n
        ret[0] = 1;
        return ret;
    }

    /**
     * 数字加一规律(当前位数是 9 就进位, 不是 9 就 +1 返回)
     * <p>
     * 时间复杂度: O(n)
     * <br>
     * 空间复杂度: 0(n)
     */
    public static int[] plusOneOptimization(int[] digits) {
        int length = digits.length;

        // 是 9 就进位, 不是 9 就 +1 返回
        for (int i = length - 1; i >= 0; i--) { // time n
            if (digits[i] != 9) {
                digits[i] = ++digits[i];
                return digits;
            } else {
                digits[i] = 0;
            }
        }

        // 全是 9
        int[] ret = new int[length + 1]; // space n
        ret[0] = 1;
        return ret;
    }

    /**
     * 数字加一规律(当前位数是 9 就进位, 不是 9 就 +1 返回)
     * <p>
     * 时间复杂度: O(n)
     * <br>
     * 空间复杂度: 0(n)
     */
    public static int[] plusOne2(int[] digits) {
        int carry = 1;
        for (int i = digits.length - 1; i >= 0 && carry != 0; --i) { // time n
            carry += digits[i];
            digits[i] = carry % 10;
            // 小数除大数得0, 10/10=1
            carry /= 10;
        }
        if (carry > 0) {
            int[] res = new int[digits.length + 1]; // space n
            res[0] = 1;
            return res;
        }
        return digits;
    }
}